#include <iostream>

using namespace std;
typedef long long LL;

void solve()
{
    LL n, k; cin >> n >> k;
    LL ans = 0;
    bool flag = true;
    // 因为初始情况也是在下面while循环算的，所以k >= 0而不是1
    while(n && k >= 0)
    { 
        if(flag) ans += 1 + k;
        else ans++;
        if(n % 2) flag = true;
        else flag = false;
        n /= 2;
        k--;
    }
    // 如果出现0while循环结束，最后我们统计上就行
    if(n == 0) ans++;
    cout << ans << endl;
}

int main()
{
    int t; cin >> t;
    while(t--)
    {
        solve();
    }
    return 0;
}